package 力扣日常刷题.木22一月.第05天0112;

/**
 * @author 帅小伙
 * @date 2022/1/12
 * @description
 */
public class Demo08回溯中等字母组合迭代器 {

    class CombinationIterator {
        private int[] pos;
        private boolean finished;
        private char[] str;
        public CombinationIterator(String characters, int combinationLength) {
            finished=false;
            pos=new int[combinationLength];
            str=characters.toCharArray();
            //第一个组合就是字符串的前combinationLength个字符
            for(int i=0;i<combinationLength;i++){
                pos[i]=i;
            }
        }

        public String next() {
            StringBuilder stringBuilder=new StringBuilder();
            //1.构造结果
            for(int index:pos){
                stringBuilder.append(str[index]);
            }
            //2.寻找下一次组合
            int flag=-1;
            //对于组合中的第 i个位置，它的最大值是字符串中的第 len - k + i 个字母；len-(k-i);
            //从后往前查看,判断是否还有字符没有到达最大位置处
            for(int i=pos.length-1;i>=0;i--){
                //不等表明还未到达最大位置处
                if(pos[i]!=str.length-pos.length+i){
                    flag=i;
                    break;
                }
            }
            //为-1表明后续没有组合了
            if(flag==-1){
                finished=true;
            }else{
                //更新组合位置信息，为下次调用next返回结果做准备
                pos[flag]++;
                //后续位置参数均为前面更新后的位置参数的后一位
                for(int j=flag+1;j<pos.length;j++){
                    pos[j]=pos[j-1]+1;
                }
            }
            return stringBuilder.toString();
        }

        public boolean hasNext() {
            return !finished;
        }
    }
}
